package com.example.leetcode.bfs;

import java.util.*;

public class leetcode310 {
    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{1, 0}, {1, 2}, {1, 3}};

        Solution solution = new Solution();
        System.out.println(solution.findMinHeightTrees(n, edges));
    }

    static class Solution {
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            if (n == 1) {
                return Collections.singletonList(0);
            }

            // 构建图
            List<Set<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                graph.add(new HashSet<>());
            }
            for (int[] edge : edges) {
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }

            // 找到所有叶子节点
            List<Integer> leaves = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (graph.get(i).size() == 1) {
                    leaves.add(i);
                }
            }

            // 剥洋葱：每轮移除叶子
            int remainingNodes = n;
            // 当结点数小于等于2个时，两个结点（或只剩下一个）都成了叶子结点，也就是中心
            while (remainingNodes > 2) {
                remainingNodes -= leaves.size();
                List<Integer> newLeaves = new ArrayList<>();

                for (int leaf : leaves) {
                    // 找到叶子结点唯一的邻居
                    int neighbor = graph.get(leaf).iterator().next();
                    // 从邻居中移除当前叶子结点
                    graph.get(neighbor).remove(leaf);
                    // 如果移除后邻居成了新的叶子结点
                    if (graph.get(neighbor).size() == 1) {
                        // 加入集合
                        newLeaves.add(neighbor);
                    }
                }

                leaves = newLeaves;
            }

            // 返回最后剩下的叶子结点
            return leaves;
        }
    }


    // 暴力BFS超时
//    static class Solution {
//        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
//            if (edges.length == 0) {
//                return Collections.singletonList(0);
//            }
//
//            Map<Integer, List<Integer>> graph = new HashMap<>();
//            for (int[] edge : edges) {
//                int u = edge[0];
//                int v = edge[1];
//                if (!graph.containsKey(u)) {
//                    graph.put(u, new ArrayList<>());
//                }
//                graph.get(u).add(v);
//
//                if (!graph.containsKey(v)) {
//                    graph.put(v, new ArrayList<>());
//                }
//                graph.get(v).add(u);
//            }
//
//            // 记录不同层次下对应的起点列表
//            Map<Integer, List<Integer>> levelMap = new HashMap<>();
//            // 当前最小层次
//            int minLevel = Integer.MAX_VALUE;
//            for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
//                Integer start = entry.getKey();
//
//                Set<Integer> visited = new HashSet<>();
//                Queue<Integer> queue = new LinkedList<>();
//
//                queue.add(start);
//                visited.add(start);
//                Integer level = 0;
//
//                while (!queue.isEmpty()) {
//                    level++;
//                    int levelSize = queue.size();
//                    for (int i = 0; i < levelSize; i++) {
//                        Integer cur = queue.poll();
//                        List<Integer> neighbors = graph.getOrDefault(cur, Collections.emptyList());
//                        for (Integer neighbor : neighbors) {
//                            if (!visited.contains(neighbor)) {
//                                queue.add(neighbor);
//                                visited.add(neighbor);
//                            }
//                        }
//                    }
//                }
//
//                if (!levelMap.containsKey(level)) {
//                    levelMap.put(level, new ArrayList<>());
//                }
//                levelMap.get(level).add(start);
//
//                if (level < minLevel) {
//                    minLevel = level;
//                }
//            }
//            return levelMap.get(minLevel);
//        }
//    }
}
